Network-attached storage (NAS) systems are generally computing-storage devices that can be accessed over a computer network, rather than being directly connected to the computer (via a computer bus). NAS systems enable multiple users to share the same storage space at once, and often minimize overhead by centrally managing hard disks. An operating system, executing on a NAS file server, controls the allocation of memory to coupled clients. Allocation is generally performed at a page granularity, where a page is a selected number of contiguous blocks. The particular size of a page is typically a function of the operating system, for example in the Data Access in Real time (DART) operating system of EMC Corporation, Hopkinton Mass., and the page size is 8K bytes.
To the operating system, the file system is a collection of 8 k blocks. As the file server is initialized, some of the pages are reserved for use by the operating system, some pages are designated as ‘free’ for allocation to other applications, and a large chunk of pages are reserved to provide a buffer cache. The buffer cache temporarily stores pages that are also stored in an attached disk device to increase application performance. File system accesses may be serviced from the buffer cache rather than read from the disk, thereby saving the delay associated with I/O disk access and increasing file server performance.
One of the functions of the file server operating system is to allocate pages to applications. The operating system maintains a ‘free list’, which is a list of pages that are available for allocation to applications. When an application requires one or more pages, the operating system may allocate a page from either the free list or the buffer cache. When client applications no longer need pages, they are returned to the free list. Because of the way that pages are added and removed from the free list, consecutive entries of the free list do not generally point to consecutive pages in memory.
The performance of applications is heavily influenced by the speed with which an application can retrieve data. As such, it is important to allocate pages to applications in an intelligent manner. For example, when applications require multiple pages for operation, it is desirable that the pages that are allocated to the application are contiguous in memory since data can be accessed from contiguous memory locations much more quickly. Because the free list can not be relied upon to provide contiguous pages, a different mechanism must be used for identifying contiguous pages of memory for allocation to applications.
One mechanism that is often used to identify contiguous pages in memory is a frame table, such as that shown in FIG. 1. A frame table stores an indication of the ‘ownership’ of each page of memory. Several exemplary indications are shown in FIG. 1. The indication may be that the page is ‘free’ (indicated by an F in FIG. 1), or that the page is in owned by the file system or by an existing application (indicated by an O in FIG. 1), or that the page has been allocated to the buffer cache (indicated by a B in FIG. 1).
Historically the frame table has been used to locate contiguous pages in the following manner. For example, as shown in FIG. 1, assume that a multiple page allocation process is seeking to identify three contiguous pages in memory to allocate to an application. First an initial free page is retrieved from the free list. In the example of FIG. 1, assume that page 0 is identified as a free page by the free list. Using the frame table, the multi-page allocation process checks the ownership status of the next consecutive page in memory, page 1 in the example of FIG. 1. The ownership bit of page 1 is also free. The multi-page allocation process then checks the ownership of the third consecutive page in memory, page 2. Unfortunately, the ownership bit in the frame table indicates that page 2 is allocated to the buffer cache (B).
Because the consecutive frame table entries (0, 1 and 2) associated with the page retrieved from the free list indicate that the memory pages will not satisfy the multi-page allocation request, the free list is again accessed to locate a different free page, to begin a consecutive free page search. In the example of FIG. 1, page 3 is retrieved from the free list, and the process next checks the ownership status of page 4. Because page 4 is in use, the process returns to the free list to retrieve another free page. In the example of FIG. 1, page 5 is returned from the free list. The multi-page allocation process checks the ownership status of page 6 and 7. Having located three consecutive free pages, the process can then allocate the application to these pages.
Although the above process may successfully identify multiple consecutive pages, the non-deterministic nature of the process makes it inefficient and time consuming. In addition, it may be eventually determined that there are not enough free consecutive pages to satisfy an allocation request. A typical solution to such a problem is to restart the allocation procedure and pre-empt, or effectively ‘steal’ the first buffer cache page identified in the frame table; effectively ‘swapping’ the page from the buffer cache to the ‘free list.’ Such blind pre-emption of buffer cache pages, however, may cause delay to an application that is using the pre-empted buffer cache page, and thrashing can occur. It would be desirable to identify an improved multi-page allocation method which overcomes the problems of the prior art.